package leetcode.editor.cn;

import arithmetic2.ListNode;
import org.apache.poi.ss.formula.ptg.NameXPtg;

//[92]反转链表 II
public class ReverseLinkedListIi92{
public static void main(String[] args) {
   Solution solution = new ReverseLinkedListIi92().new Solution();
   
}

  //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //反转点的 cache
        ListNode current = head;
        ListNode pri = null;

        //记录开始、结束的节点
        int currentIndex = 1;
        ListNode priLeft = null;//left-1
        ListNode leftNode = null;
        ListNode rightNode = null;
        ListNode lastRight = null;//right+1

        while (current!=null){//3，5 执行了  5-》3，没有执行  3-》null 因为 current 5.next is null
            ListNode next = current.next;
            if (left-1 == currentIndex){//origin left-1,边界 1的话就是 null
                priLeft = current;
            }
            if (left == currentIndex){// origin left
                leftNode = current;
            }
            if (right == currentIndex){//origin right
                rightNode = current;
            }

            if (right+1 == currentIndex){//origin right+1
                lastRight = current;
                if (leftNode!=null){
                    leftNode.next = lastRight;//更改指向 origin left-> right+1
                }
                if (priLeft !=null){
                    priLeft.next = rightNode;//更改指向 origin left-1->right
                }
                break;//这是最后需要反转的点 break
            }
            if (left < currentIndex && currentIndex <= right){//找到开始反转的点
                //reverse
                current.next = pri;//reverse
            }

            pri = current;// cache
            current = next;// foreach point
            currentIndex++;
        }

        //while 循环null进不来 .【3，5】1 2 当 current 在5后边时
        if (current == null && right+1 == currentIndex){//n+1 就是null, 全部反转。
            lastRight = current;//origin right + 1
            if (leftNode!=null){
                leftNode.next = lastRight;//更改指向 origin left-> right+1
            }
            if (priLeft !=null){
                priLeft.next = rightNode;//更改指向 origin left-1->right
            }
        }

        //返回 head
        if (left>1){
            return head;
        }
        return rightNode;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}